The present invention relates generally to the field of distributed computing, and more particularly to task scheduling and management of parent-child and recursive tree computational workloads.
In grid computing, the parent-child workload pattern is one in which an initial client process will submit one or more tasks to the workload scheduler to be computed in parallel and asynchronously on the grid. Tasks are computations that can be executed in parallel in a grid or a cluster of computing devices. A task runs on a service instance. Service instances are self-contained processes performing computation or logic. The execution of a task is by one or more threads of a process of a service instance.
Each submitted task may further decompose into smaller sub-tasks that can also be submitted to the scheduler to be run in parallel and asynchronously on the grid. Task decomposition can occur for many levels or what are sometimes referred to as “generations” of tasks. Decomposition of tasks for many levels in which parent tasks have dependencies on child tasks are referred to as “recursive decomposition”.
Tasks that decompose into sub-tasks are “parent tasks” to their sub-tasks. The sub-tasks of a parent task are known as “child tasks” of the parent task. A “root” task is the task directly submitted by a client to the grid computing environment, and does not have a parent task. The full decomposition of the root task into all of its generations of sub-tasks can be compared to the structure of an inverted tree, in which the leaves of the tree correspond to child tasks that have no children tasks or sub-tasks of their own.
The workflow pattern of the inverted parent-child tree structure has a characteristic in which the parent task has a dependency on its corresponding child task(s). Before the parent task can generate a result, the child task(s) must complete and provide results to the parent task.